#ifndef ADJIACENCY_MATRIX_H
#define ADJIACENCY_MATRIX_H

#include <iostream>
#include <vector>
#include <cassert>



/**
 * 图的邻接矩阵表示
 * 矩阵的元素表示边的权重（有权图）或存在（无权图）
 */

// V -- 图顶点的数据类型
template<typename V>
class Adjiacency_Matrix
{
private:
    typedef std::vector<std::vector<double>> doubleMatrixType;
    bool isDirected; /// 标识是否是有向图，默认为false
    bool isWeighted; /// 标识是否是有权图，默认为false
    double invalidWeight; /// 无效权重，用户初始化时指定，默认为0
    size_t size; /// 顶点个数
    std::vector<V> vertices; /// 存储顶点
    doubleMatrixType matrix; /// 邻接矩阵

    // 获取顶点的索引
    int  getIndexOfVertex(const V & _vertex);

public:
    // 构造函数
    Adjiacency_Matrix(const std::vector<V> & _vertices, bool _isDirected = false, bool _isWeighted = false, double _invalidWeight = 0);
    // 向图中添加一条边
    void add_edge(const V & v1, const V & v2); /// 无权图，边存在为1，不存在为0
    void add_edge(const V & v1, const V & v2, double weight); /// 有权图，权重为invalidWeight表示边不存在
    // 输出图中所有顶点
    void list_vertices();
    // 输出图中所有边
    void list_edges();
    // 打印整个图
    void print_graph();
    // 图的顶点个数
    size_t num_vertices()
	{
	    return size;
	}
    // 图的边数
    size_t num_edges();
    
};

// 构造函数并初始化数据
template<typename V>
Adjiacency_Matrix<V>::Adjiacency_Matrix(const std::vector<V> & _vertices, bool _isDirected, bool _isWeighted, double _invalidWeight)
    : vertices{_vertices}, isDirected{_isDirected}, isWeighted{_isWeighted}, invalidWeight{_invalidWeight}
{
    size = vertices.size();
    // 无权图
    if(!isWeighted)
    {
	doubleMatrixType _matrix(size,std::vector<double>(size,0.0));
	matrix = _matrix;
    }
    else // 有权图
    { 
	doubleMatrixType _matrix(size,std::vector<double>(size,invalidWeight));
        matrix = _matrix;
    }
}

// 无权图
template<typename V>
void Adjiacency_Matrix<V>::add_edge(const V & v1, const V & v2)
{
    // 只有无权图才能使用
    if(isWeighted)
    {
	std::cerr << "This is an unweighted graph!" << std::endl;
	assert(false);
    }
    
    int start = getIndexOfVertex(v1);
    int end = getIndexOfVertex(v2);

    matrix[start][end] = 1.0;

    // 如果是无向图，还需要补充对称点的信息
    if (!isDirected)
    {
	// 无向图不能有loop
	if(start == end)
	{
	    std::cerr << "Undirected graph can't have a loop!" << std::endl;
	    assert("false");
	}
	matrix[end][start] = 1.0;
    }

    /**
     * 其他元素在初始化时都为0
     */
}

// 有权图
template<typename V>
void Adjiacency_Matrix<V>::add_edge(const V & v1, const V & v2, double weight)
{
    // 只有有权图才能使用
    if(!isWeighted)
    {
	std::cerr << "This is a weighted graph!" << std::endl;
	assert(false);
    }

    int start = getIndexOfVertex(v1);
    int end = getIndexOfVertex(v2);

    matrix[start][end] = weight;

    // 如果是无向图，还需要补充对称点的信息
    if (!isDirected)
    {
	// 无向图不能有loop
	if(start == end)
	{
	    std::cerr << "Undirected graph can't have a loop!" << std::endl;
	    assert("false");
	}
	matrix[end][start] = weight;
    }	
}

template<typename V>
void Adjiacency_Matrix<V>::list_vertices()
{
    std::cout << "vertex set:\t";
    for(const auto & v : vertices)
	std::cout << v << " ";
    std::cout << "\b" << std::endl;
}

template<typename V>
void Adjiacency_Matrix<V>::list_edges()
{
    std::cout << "edge set:\t";

    // 无向图，遍历下三角
    if(!isDirected)
    {
	// 无权图
	if (!isWeighted)
	{
	    for(int i = 0; i < size; ++i)
		for(int j = 0; j < i; ++j) /// 无向图没有loop，因此无需遍历对角线元素
		    if(matrix[i][j] != 0)
			std::cout << "(" << vertices[i] << "," << vertices[j] << ") ";
	    std::cout << "\b" << std::endl;
	}
	else{ // 有权图	
	    for(int i = 0; i < size; ++i)
		for(int j = 0; j < i; ++j)
		    if(matrix[i][j] != invalidWeight)
			std::cout << "(" << vertices[i] << "," << vertices[j] << "," << matrix[i][j] << ") ";
	    std::cout << "\b" << std::endl;
	}	
    }
    else{  // 有向图，遍历整个矩阵
	// 无权图
	if(!isWeighted)
	{
	    for(int i = 0; i < size; ++i)
		for(int j = 0; j < size; ++j)
		    if(matrix[i][j] != 0)
			std::cout << "(" << vertices[i] << "," << vertices[j] << ") ";
	    std::cout << "\b" << std::endl;	
	}
	else{ // 有权图
	    for(int i = 0; i < size; ++i)
		for(int j = 0; j < size; ++j)
		    if(matrix[i][j] != invalidWeight)
			std::cout << "(" << vertices[i] << "," << vertices[j] << "," << matrix[i][j] << ") ";
	    std::cout << "\b" << std::endl;	
	}
    }	
}

template<typename V>
void Adjiacency_Matrix<V>::print_graph()
{
    std::cout << "graph:" << std::endl;

    // 无向图
    if(!isDirected)
    {
	// 无权图
	if (!isWeighted)
	{
	    for(int i = 0; i < size; ++i)
	    {
		std::cout << vertices[i] << " <--> ";
		for(int j = 0; j < size; ++j) 
		    if(matrix[i][j] != 0)
			std::cout << vertices[j] << " ";
		std::cout << "\b" << std::endl;
	    }
	}
	else{ // 有权图	
	    for(int i = 0; i < size; ++i)
	    {
		std::cout << vertices[i] << " <--> ";
		for(int j = 0; j < size; ++j) 
		    if(matrix[i][j] != invalidWeight)
			std::cout << "(" << vertices[j] << "," << matrix[i][j] << ") ";
		std::cout << "\b" << std::endl;
	    }
	}	
    }
    else{  // 有向图
	// 无权图
	if(!isWeighted)
	{
	    for(int i = 0; i < size; ++i)
	    {
		std::cout << vertices[i] << " --> ";
		for(int j = 0; j < size; ++j)
		    if(matrix[i][j] != 0)
			std::cout << vertices[j] << " ";
		std::cout << "\b" << std::endl;
	    }
	}
	else{ // 有权图
	    for(int i = 0; i < size; ++i)
	    {
		std::cout << vertices[i] << " --> ";
		for(int j = 0; j < size; ++j)
		    if(matrix[i][j] != invalidWeight)
			std::cout << "(" << vertices[j] << "," << matrix[i][j] << ") ";
		std::cout << "\b" << std::endl;
	    }
	}
    }
	
}

template<typename V>
size_t Adjiacency_Matrix<V>::num_edges()
{
    size_t cnt = 0;

    // 无向图，遍历下三角
    if(!isDirected)
    {
	// 无权图
	if (!isWeighted)
	{
	    for(int i = 0; i < size; ++i)
		for(int j = 0; j < i; ++j) /// 无向图没有loop，因此无需遍历对角线元素
		    if(matrix[i][j] != 0)
			++cnt;
	}
	else{ // 有权图	
	    for(int i = 0; i < size; ++i)
		for(int j = 0; j < i; ++j)
		    if(matrix[i][j] != invalidWeight)
			++cnt;

	}	
    }
    else{  // 有向图，遍历整个矩阵
	// 无权图
	if(!isWeighted)
	{
	    for(int i = 0; i < size; ++i)
		for(int j = 0; j < size; ++j)
		    if(matrix[i][j] != 0)
			++cnt;

	}
	else{ // 有权图
	    for(int i = 0; i < size; ++i)
		for(int j = 0; j < size; ++j)
		    if(matrix[i][j] != invalidWeight)
			++cnt;

	}
    }

    return cnt;
}

template<typename V>
int Adjiacency_Matrix<V>::getIndexOfVertex(const V & v)
{
    for (int idx = 0; idx < size; ++idx)
    {
        if (vertices[idx] == v)
            return idx;
    }

    // 如果没有找到就说明发生了错误
    assert(false);
    return -1;
}


#else
#endif
